๐Ÿ‘ฉโ€๐Ÿ’ป 60057. ๋ฌธ์ž์—ด ์••์ถ•

@Seongukbaek Posted June 11, 2022 ยท Updated June 11, 2022 ยท 3 min read

๋ฌธ์ œ

Programmers - ๋ฌธ์ž์—ด ์••์ถ•

๐Ÿ“ Logic

// ์ „์ฒด ๋ฐ˜๋ณต์€ s ๊ธธ์ด์˜ ์ ˆ๋ฐ˜๊นŒ์ง€๋งŒ for (int len = 1; len <= inputLength / 2; len++) { int length = 0; int idx = 0; // ์ž๋ฅผ word๊ฐ€ s์˜ ๋ฒ”์œ„ ์•ˆ์— ์žˆ๋Š” ๊ฒฝ์šฐ๊นŒ์ง€ ๋ฐ˜๋ณต while(idx + len <= inputLength) { String word = getWord(idx, len); int count = 0; // ํ™•์ธํ•  ๋ฌธ์ž์—ด์ด s์˜ ๋ฒ”์œ„ ์•ˆ์— ์žˆ๊ณ , ๊ทธ ๋ฌธ์ž์—ด์ด word์™€ ๋™์ผํ•œ ๊ฒฝ์šฐ // ๊ทธ ๋ฌธ์ž์—ด์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•œ๋‹ค. while (idx + len <= inputLength && word.equals(getWord(idx, len))) { idx += len; count++; } // count๊ฐ€ 1์ด๋ฉด ๋ฌธ์ž์—ด ๊ธธ์ด๋งŒ ๋”ํ•˜๊ณ , 1๋ณด๋‹ค ํฐ ๊ฒฝ์šฐ์—๋Š” ๊ทธ ๊ธธ์ด๋„ ํ•จ๊ป˜ ๋”ํ•œ๋‹ค. length += word.length() + (count > 1 ? String.valueOf(count).length() : 0); } // ๋‚จ์€ ๋ฌธ์ž์—ด ๋ถ™์ด๊ธฐ length += inputLength - idx; minLength = Math.min(minLength, length); }
  • ๋ฌธ์ž์—ด์€ 1๋ถ€ํ„ฐ ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด ๊ธธ์ด์˜ ์ ˆ๋ฐ˜๊นŒ์ง€๋งŒํผ ์ž๋ฅด๋Š” ๊ฒƒ์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
  • ์ •ํ•œ ๊ธธ์ด๋งŒํผ ๋ฌธ์ž์—ด์„ ๋น„๊ตํ•˜๊ณ  ๊ฐœ์ˆ˜์™€ ์ •ํ•œ ๊ธธ์ด๋งŒํผ์„ length ์— ๋”ํ•ด, ์ตœ์ข…์ ์œผ๋กœ minLength ๋ฅผ ์ตœ์‹ ํ™”ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { static String inputString; public int solution(String s) { if (s.length() == 1) return 1; inputString = s; int inputLength = s.length(); int minLength = Integer.MAX_VALUE; // ์ „์ฒด ๋ฐ˜๋ณต์€ s ๊ธธ์ด์˜ ์ ˆ๋ฐ˜๊นŒ์ง€๋งŒ for (int len = 1; len <= inputLength / 2; len++) { int length = 0; int idx = 0; // ์ž๋ฅผ word๊ฐ€ s์˜ ๋ฒ”์œ„ ์•ˆ์— ์žˆ๋Š” ๊ฒฝ์šฐ๊นŒ์ง€ ๋ฐ˜๋ณต while(idx + len <= inputLength) { String word = getWord(idx, len); int count = 0; // ํ™•์ธํ•  ๋ฌธ์ž์—ด์ด s์˜ ๋ฒ”์œ„ ์•ˆ์— ์žˆ๊ณ , ๊ทธ ๋ฌธ์ž์—ด์ด word์™€ ๋™์ผํ•œ ๊ฒฝ์šฐ // ๊ทธ ๋ฌธ์ž์—ด์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•œ๋‹ค. while (idx + len <= inputLength && word.equals(getWord(idx, len))) { idx += len; count++; } // count๊ฐ€ 1์ด๋ฉด ๋ฌธ์ž์—ด ๊ธธ์ด๋งŒ ๋”ํ•˜๊ณ , 1๋ณด๋‹ค ํฐ ๊ฒฝ์šฐ์—๋Š” ๊ทธ ๊ธธ์ด๋„ ํ•จ๊ป˜ ๋”ํ•œ๋‹ค. length += word.length() + (count > 1 ? String.valueOf(count).length() : 0); } // ๋‚จ์€ ๋ฌธ์ž์—ด ๋ถ™์ด๊ธฐ length += inputLength - idx; minLength = Math.min(minLength, length); } return minLength; } private String getWord(int start, int len) { return inputString.substring(start, start + len); } }

โœ๏ธ Review

  • ์ œ์ผ ๋จผ์ € ๊ทธ๋ฆฌ๋””ํ•œ ๋ฐฉ๋ฒ•์„ ๋– ์˜ฌ๋ฆฌ๊ธด ํ–ˆ์œผ๋‚˜, ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜์ง€ ์•Š์„๊นŒ ์ƒ๊ฐํ–ˆ๋‹ค.
  • ๋ฌธ์ž์—ด์„ ๊ธธ์ด๊ฐ€ ์ตœ๋Œ€ 1000์ด์—ˆ๊ณ , ์–ด์ฐจํ”ผ ๋ฌธ์ž์—ด ๋น„๊ต๋ฅผ ์œ„ํ•ด ์ ˆ๋ฐ˜ ๊ธธ์ด๊นŒ์ง€๋งŒ ์ž๋ฅผ ๊ฒƒ์ด๋ฏ€๋กœ ๊ดœ์ฐฎ์„ ๊ฒƒ ๊ฐ™์•˜๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€